package hot100;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class IsValidBST {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean isValidBST(TreeNode root) {
        //中序遍历二叉树，放入集合
        List<Integer> list = new ArrayList<>();
        inOrder(root,list);
        //判断集合是否有序
        return isSorted(list);
    }

    private boolean isSorted(List<Integer> list) {
        Integer pre = null;
        for (Integer item : list) {
            if (pre == null) {
                pre = item;
                continue;
            }
            if (item <= pre) return false;
            pre = item;
        }

        return true;
    }

    private void inOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;

        inOrder(root.left,list);

        list.add(root.val);

        inOrder(root.right,list);
    }

    public TreeNode constructTree(Integer[] arr,int index) {
        if (index >= arr.length || arr[index] == null) return null;
        TreeNode node = new TreeNode(arr[index]);
        node.left = constructTree(arr,2 * index + 1);
        node.right = constructTree(arr,2 * index + 2);
        return node;
    }

    @Test
    public void test() {
        TreeNode root = constructTree(new Integer[]{5, 1, 4, null, null, 3, 6}, 0);
        System.out.println(isValidBST(root));
    }


}
